
/*
 * Created by guoyh on Sat Jan 07 2023 21:31:25
 * leetcode NO.16 https://leetcode.cn/problems/3sum-closest/
 * 最接近的三数之和
 * 暴力法，虽正确但是性能原因无法在leetcode AC
 */

#include <iostream>
#include <gtest/gtest.h>
using namespace std;

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        if(nums.size() == 3) return nums[0] + nums[1] + nums[2];
        int minx = INT_MAX;
        int sum = 0;
        for(int i = 0; i < nums.size(); i++)
            for(int j = i+1; j < nums.size(); j++)
                for(int k = j+1; k < nums.size(); k++){
                    if(abs(nums[i] + nums[j] + nums[k] - target) < minx){
                        sum = nums[i] + nums[j] + nums[k];

                        minx = abs(sum - target);
                        if(sum - target > 0){
                            sum = minx + target;
                        }else{
                            sum = target - minx;
                        }
                    }
                }
        return sum;
    }
};


int add(int a, int b) {
    return a + b;
}

TEST(MyTest, AddTest) {
    EXPECT_EQ(add(1, 2), 3);
}

TEST(MyTest, test01){
    vector<int> v = {-1,2,1,-4};
    Solution slu;
    
    ASSERT_EQ(slu.threeSumClosest(v, 1), 2);
}


TEST(MyTest, test02){
    vector<int> v = {-213,-259,263,540,-632,-401,257,673,29,-737,-478,-193,-90,651,620,353,232,-358,-588,233,-946,-231,422,239,143,648,-994,603,509,361,-122,-295,-671,472,-982,-483,-533,-28,-403,869,499,-736,559,245,-148,970,50,944,857,939,737,911,-577,142,-20,109,719,-377,586,201,160,-141,323,183,665,839,-127,-979,-668,368,744,575,-452,-487,-649,-321,546,371,-665,-83,580,487,-883,421,-456,-907,111,779,633,-146,929,55,950,866,-941,-881,-606,528,-708,-991,910,579,-419,-270,-317,-40,-192,300,-760,-119,897,-536,25,-57,-831,-52,-315,-913,-212,738,167,-319,-652,-115,221,-764,-349,680,-31,-617,924,868,397,-421,789,-35,590,536,-763,282,-229,302,-990,-467,-230,974,464,-835,-21,116,975,79,-792,-187,-765,380,-529,-339,609,676,-910,-275,780,311,-598,38,681,-418,995,-904,-108,-381,-877,-570,847,-780,639,383,443,-842,592,-858,-811,440,296,-527,-905,-485,490,-523,-987,567,647,482,965,-638,359,-535,449,358,36,810,-223,-906,999,-1000,-969,878,853,-359,-544,865,-664,-919,-681,15,-673,448,-109,98,428,-25,-841,616,-14,-43,-768,372,406,-372,972,396,-214,-336,106,-209,340,258,877,800,-137,-738,149,-887,-962,-872,-689,501,-462,45,-518,-107,-388,-534,945,-202,-687,-468,303,921,312,-567,-188,876,542,606,988,107,533,387,-210,410,-986,327,888,-722,-375,252,785,-563,-37,-955,-333,-810,486,278,-180,-876,-350,566,454,289,548,-240,-729,320,-622,178,-113,883,-168,173,-934,-493,788,736,572,331,-725,463,-677,394,194,671,-574,-761,823,309,684,-509,458,-140,273,-825,519,119,-956,419,774,-837,-151,858,882,893,209,-801,666,-476,157,41,556,-238,-164,-402,-499,-447,-556,-44,313,-482,-449,412,-849,758,465,-264,-582,-853,-846,456,-280,-601,-819,756,-957,919,466,415,238,-6,732,373,105,-850,-135,-783,-555,-128,-144,-609,-470,128,-248,-659,-971,148,-775,-139,-788,-585,-36,695,442};
    Solution slu;
    int res = slu.threeSumClosest(v, -5443);
    cout<<res<<endl;
    ASSERT_EQ(res, -2985);
}

TEST(MyTest, test03){
    vector<int> v = {-749,-694,-845,776,-488,-280,-144,-71,740,-766,795,-615,856,-970,-946,184,-157,798,493,-334,-779,-414,-63,-825,802,-732,-378,-588,-680,-447,-27,-792,672,-541,55,-227,378,566,-332,67,914,-672,-707,159,225,-526,273,164,806,-744,-494,63,-740,868,-36,-777,498,-872,-20,314,889,535,373,-990,-102,161,263,-207,-592,843,182,-212,-175,-268,-247,431,-644,896,298,858,103,-854,239,938,2,318,-823,-39,-28,-622,-357,-2,581,992,-182,119,-32,-59,-524,-173,916,772,-287,-331,389,-511,808,-139,654,756,-641,-197,269,443,-393,-605,394,-484,736,-842,-314,-455,706,-960,333,-343,398,491,-916,-887,118,444,85,-812,-630,-169,-799,-625,755,888,-636,-545,552,343,709,211,729,-576,-879,344,879,227,563,460,293,-734,-631,-886,331,748,-940,62,50,135,-867,602,549,413,-241,404,-286,875,346,319,-256,-232,432,-415,45,768,210,541,595,-930,820,390,-976,-709,-741,861,-921,882,-697,-985,-335,590,-133,-611,835,34,131,-754,177,902,-669,283,456,-885,-711,-725,207,969,-665,671,489,-271,658,-19,-954,-575,-857,-289,-246,-147,-336,-128,311,371,958,531,-148,277,-429,511,-951,855,803,127,-67,-229,890,-249,69,-244,903,382,-522,428,574,-721,-924,-328,-677,-140,312,-861,-942,761,-454,569,-968,935,-654,-234,-472,-518,-129,100,285,663,-980,-590,-762,-830,-152,-309,-579,481,-751,-46,-209,155,339,-870,-865,194,393,800,649,680,-180,219,-863,192,-397,-648,513,-578,930,223,704,-119,-204,746,-308,217,-604,368,-983,-13,-597,419,751,421,-290,160,805,433,3,268,178,-292,-298,167,753,-801,-848,-859,-382,790,248,-902,908,-723,18,41,374,-668,534,4,396,326,559,150,-923,482,-233,-270,425,-92,757,593,218,299,27,-619,993,-462,-849,-598,-386,503,801,-975,322,126,-45,964,-831,-220,15,1000,46,-841,-38,-371,232,-907,77,-374,412,-760,612,-620,-646,-929,323,410,-163,402,-685,452,758};
    Solution slu;
    int res = slu.threeSumClosest(v, -5977);
    cout<<res<<endl;
    ASSERT_EQ(res, -2958);
}

int main(int argc, char *argv[]) {
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}
